Median of two sorted arrays

Time: O(Log(min(M,N))); Space: O(1); hard

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Clarification:

• The definition of the median:

  • The median here is equivalent to the median in the mathematical definition.

  • The median is the middle of the sorted array.

  • If there are n numbers in the array and n is an odd number, the median is A[(n-1)/2].

  • If there are n numbers in the array and n is even, the median is (A[n / 2] + A[n / 2 + 1]) / 2.

• For example, the median of the array A=[1,2,3] is 2, and the median of the array A=[1,19] is 10.

Example 1:

Input: nums1 = [1,3], nums2 = [2]

Output: 2.00000

Explanation:

• merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]

Output: 2.50000

Explanation:

• merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]

Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]

Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []

Output: 2.00000

Constraints:

• len(nums1) == m

• len(nums2) == n

• 0 <= m <= 1000

• 0 <= n <= 1000

• 1 <= m + n <= 2000

• -106 <= nums1[i], nums2[i] <= 106

Follow up:

• The overall run time complexity should be O(log (m+n)).

1. Binary Search [O(Log(min(M,N))), O(1)]

class Solution1(object):
    """
    Time: O(Log(min(M,N)))
    Space: O(1)
    """
    def getKth(self, A, B, k):
        m, n = len(A), len(B)
        if m > n:
            return self.getKth(B, A, k)

        left, right = 0, m
        while left < right:
            mid = left + (right - left) // 2
            if 0 <= k - 1 - mid < n and A[mid] >= B[k - 1 - mid]:
                right = mid
            else:
                left = mid + 1

        Ai_minus_1 = A[left - 1] if left - 1 >= 0 else float("-inf")
        Bj = B[k - 1 - left] if k - 1 - left >= 0 else float("-inf")

        return max(Ai_minus_1, Bj)

    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        len1, len2 = len(nums1), len(nums2)
        if (len1 + len2) % 2 == 1:
            return self.getKth(nums1, nums2, (len1 + len2)//2 + 1)
        else:
            return (self.getKth(nums1, nums2, (len1 + len2)//2) +
                    self.getKth(nums1, nums2, (len1 + len2)//2 + 1)) * 0.5

s = Solution1()

nums1 = [1,3]
nums2 = [2]
assert s.findMedianSortedArrays(nums1, nums2) == 2.00000

nums1 = [1,2]
nums2 = [3,4]
assert s.findMedianSortedArrays(nums1, nums2) == 2.50000

nums1 = [0,0]
nums2 = [0,0]
assert s.findMedianSortedArrays(nums1, nums2) == 0.00000

nums1 = []
nums2 = [1]
assert s.findMedianSortedArrays(nums1, nums2) == 1.00000

nums1 = [2]
nums2 = []
assert s.findMedianSortedArrays(nums1, nums2) == 2.00000

2. Generic solution [O(Log(max(M,N)) x Log(max_val - min_val)), O(1)]

class Solution_Generic(object):
    """
    Time:  O(Log(max(M,N)) * Log(max_val - min_val))
    Space: O(1)
    """
    def getKth(self, arrays, k):
        def binary_search(array, left, right, target, compare):
            while left <= right:
                mid = left + (right - left) // 2
                if compare(array, mid, target):
                    right = mid - 1
                else:
                    left = mid + 1
            return left

        def match(arrays, num, target):
            res = 0
            for array in arrays:
                if array:
                    res += binary_search(array, 0, len(array) - 1, num,
                                         lambda array, x, y: array[x] > y)
            return res >= target

        left, right = float("inf"), float("-inf")
        for array in arrays:
            if array:
                left = min(left, array[0])
                right = max(right, array[-1])

        return binary_search(arrays, left, right, k, match)

    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        len1, len2 = len(nums1), len(nums2)
        if (len1 + len2) % 2 == 1:
            return self.getKth([nums1, nums2], (len1 + len2)//2 + 1)
        else:
            return (self.getKth([nums1, nums2], (len1 + len2)//2) +
                    self.getKth([nums1, nums2], (len1 + len2)//2 + 1)) * 0.5

s = Solution_Generic()

nums1 = [1,3]
nums2 = [2]
assert s.findMedianSortedArrays(nums1, nums2) == 2.00000

nums1 = [1,2]
nums2 = [3,4]
assert s.findMedianSortedArrays(nums1, nums2) == 2.50000

nums1 = [0,0]
nums2 = [0,0]
assert s.findMedianSortedArrays(nums1, nums2) == 0.00000

nums1 = []
nums2 = [1]
assert s.findMedianSortedArrays(nums1, nums2) == 1.00000

nums1 = [2]
nums2 = []
assert s.findMedianSortedArrays(nums1, nums2) == 2.00000

3.

class Solution3(object):

    def findMedianSortedArrays(self, A, B):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        if A is None and B is None:
            return -1.0
        lenA = len(A)
        lenB = len(B)
        lenn = lenA + lenB

        indexA,indexB,indexC = 0,0,0
        C = [False for i in range(lenn)]
        while indexA < lenA and indexB < lenB:
            if A[indexA] < B[indexB]:
                C[indexC] = A[indexA]
                indexC += 1
                indexA += 1
            else:
                C[indexC] = B[indexB]
                indexC += 1
                indexB += 1

        while indexA < lenA:
            C[indexC] = A[indexA]
            indexC += 1
            indexA += 1

        while indexB < lenB:
            C[indexC] = B[indexB]
            indexC += 1
            indexB += 1

        indexM1 = (lenn - 1) // 2
        indexM2 = lenn // 2

        if (lenn % 2 == 0):
            return (C[indexM1] + C[indexM2]) / 2.0
        else:
            return C[indexM2] / 1.0

s = Solution3()

nums1 = [1,3]
nums2 = [2]
assert s.findMedianSortedArrays(nums1, nums2) == 2.00000

nums1 = [1,2]
nums2 = [3,4]
assert s.findMedianSortedArrays(nums1, nums2) == 2.50000

nums1 = [0,0]
nums2 = [0,0]
assert s.findMedianSortedArrays(nums1, nums2) == 0.00000

nums1 = []
nums2 = [1]
assert s.findMedianSortedArrays(nums1, nums2) == 1.00000

nums1 = [2]
nums2 = []
assert s.findMedianSortedArrays(nums1, nums2) == 2.00000

4. Recursive Approach

class Solution4(object):
    """
    Time: O(Log(min(m,n))). At first, the searching range is [0, m][0,m].
                            And the length of this searching range will be reduced by half after each loop.
                            So, we only need Log(m) loops.
                            Since we do constant operations in each loop, so the time complexity is O(Log(m)).
                            Since m <= n, so the time complexity is O(Log(min(m,n))).
    Space: O(1). We only need constant memory to store 99 local variables, so the space complexity is O(1).
    """
    def findMedianSortedArrays(self, A, B):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m, n = len(A), len(B)
        if m > n:
            A, B, m, n = B, A, n, m
        if n == 0:
            raise ValueError

        imin, imax, half_len = 0, m, (m + n + 1) // 2
        while imin <= imax:
            i = (imin + imax) // 2
            j = half_len - i
            if i < m and B[j-1] > A[i]:
                # i is too small, must increase it
                imin = i + 1
            elif i > 0 and A[i-1] > B[j]:
                # i is too big, must decrease it
                imax = i - 1
            else:
                # i is perfect

                if i == 0: max_of_left = B[j-1]
                elif j == 0: max_of_left = A[i-1]
                else: max_of_left = max(A[i-1], B[j-1])

                if (m + n) % 2 == 1:
                    return max_of_left

                if i == m: min_of_right = B[j]
                elif j == n: min_of_right = A[i]
                else: min_of_right = min(A[i], B[j])

                return (max_of_left + min_of_right) / 2.0

s = Solution4()

nums1 = [1,3]
nums2 = [2]
assert s.findMedianSortedArrays(nums1, nums2) == 2.00000

nums1 = [1,2]
nums2 = [3,4]
assert s.findMedianSortedArrays(nums1, nums2) == 2.50000

nums1 = [0,0]
nums2 = [0,0]
assert s.findMedianSortedArrays(nums1, nums2) == 0.00000

nums1 = []
nums2 = [1]
assert s.findMedianSortedArrays(nums1, nums2) == 1.00000

nums1 = [2]
nums2 = []
assert s.findMedianSortedArrays(nums1, nums2) == 2.00000

See also:

https://leetcode.com/problems/median-of-two-sorted-arrays

https://www.lintcode.com/problem/median-of-two-sorted-arrays/description

Related problems:

https://www.lintcode.com/problem/median

https://www.lintcode.com/problem/find-median-from-data-stream

https://www.lintcode.com/problem/median-of-k-sorted-arrays